﻿//1.01背包
//https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
//解法：
//方案1：不要求装满背包
//状态定义：dp[i][j] 表示前i件物品，背包容量不超过j时能获得的最大价值
//状态转移：
//不选第i件物品：dp[i][j] = dp[i - 1][j]
//选第i件物品：dp[i][j] = dp[i - 1][j - v[i]] + w[i]（如果容量足够）
//初始化：所有状态初始化为0，表示任何容量都可以从空背包开始
//方案2：要求恰好装满背包
//关键区别：初始化方式不同
//状态定义：dp[i][j] 表示前i件物品，背包容量恰好为j时能获得的最大价值
//初始化：
//dp[0][0] = 0：容量为0时，价值为0（合法状态）
//dp[0][j] = -1（j > 0）：没有物品时，任何非零容量都是不可达的
//状态转移：只有当j - v[i]容量可达（不为 - 1）时，才能选择当前物品
//#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n, V;
    cin >> n >> V;
    vector<vector<int>> dp(n + 1, vector<int>(V + 1));
    // 物品体积
    vector<int> v(n + 1);
    // 物品价值
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // ========== 方案1：不要求装满背包 ==========
    // 遍历物品
    for (int i = 1; i <= n; i++)        
        // 遍历背包容量
        for (int j = 1; j <= V; j++)   
        {
            // 不选第i件物品
            dp[i][j] = dp[i - 1][j];
            // 如果背包容量足够，考虑选第i件物品
            if (j - v[i] >= 0)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    // 输出最大价值
    cout << dp[n][V] << endl;
    // ========== 方案2：要求恰好装满背包 ==========
    // 重新初始化dp数组
    dp.assign(n + 1, vector<int>(V + 1));
    // 关键区别：初始化时，只有容量为0时是合法状态（价值为0）
    // 其他容量初始化为-1，表示不可达状态
    for (int j = 1; j <= V; j++)   dp[0][j] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= V; j++)
        {
            // 不选第i件物品
            dp[i][j] = dp[i - 1][j];
            // 只有当j-v[i]容量可达时，才能选择第i件物品
            if (j - v[i] >= 0 && dp[i - 1][j - v[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    // 如果最终状态不可达，输出0；否则输出最大价值
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
    return 0;
}



//2.分割等和子集
//https://leetcode.cn/problems/partition-equal-subset-sum/
//给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
//示例 1：
//输入：nums = [1, 5, 11, 5]
//输出：true
//解释：数组可以分割成[1, 5, 5] 和[11] 。
//示例 2：
//输入：nums = [1, 2, 3, 5]
//输出：false
//解释：数组不能分割成两个元素和相等的子集。
//提示：
//1 <= nums.length <= 200
//1 <= nums[i] <= 100



//解法：计算数组所有元素的总和sum
//如果 sum 是奇数，直接返回 false（无法平分）
//如果 sum 是偶数，问题转化为：能否从数组中选出一些元素，使它们的和等于 sum / 2
//dp[i][j]表示:能否从数组的前 i 个元素中选出一些数，使它们的和等于 j
//对于每个元素 nums[i-1](注意索引偏移)
//不选当前元素：dp[i][j] = dp[i - 1][j]
//选当前元素：如果 j >= nums[i - 1]，则 dp[i][j] = dp[i - 1][j - nums[i - 1]]
//两种情况只要有一种为真，dp[i][j] 就为真。

class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int n = nums.size();
        int sum = 0;
        // 计算数组总和
        for (auto& num : nums) sum += num;
        // 如果总和是奇数，不可能平分
        if (sum % 2 == 1) return false;
        // dp[i][j]: 能否用前i个元素凑出和j
        vector<vector<bool>> dp(n + 1, vector<bool>(sum / 2 + 1));
        // 初始化：和为0总是可以达成（不选任何元素）
        for (int i = 0; i <= n; i++) dp[i][0] = true;
        // 遍历前i个元素
        for (int i = 1; i <= n; i++)
            // 遍历目标和
            for (int j = 1; j <= sum / 2; j++)
            {
                // 情况1：不选当前元素nums[i-1]
                dp[i][j] = dp[i - 1][j];
                // 情况2：选当前元素nums[i-1]（前提是j足够大）
                if (j - nums[i - 1] >= 0)
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
            }
        return dp[n][sum / 2];


    }
};



//3.目标和
//https://leetcode.cn/problems/target-sum/description/
//给你一个非负整数数组 nums 和一个整数 target 。
//向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
//例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
//返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
//示例 1：
//输入：nums = [1, 1, 1, 1, 1], target = 3
//输出：5
//解释：一共有 5 种方法让最终目标和为 3 。
//- 1 + 1 + 1 + 1 + 1 = 3
//+ 1 - 1 + 1 + 1 + 1 = 3
//+ 1 + 1 - 1 + 1 + 1 = 3
//+ 1 + 1 + 1 - 1 + 1 = 3
//+ 1 + 1 + 1 + 1 - 1 = 3
//示例 2：
//输入：nums = [1], target = 1
//输出：1
//提示：
//1 <= nums.length <= 20
//0 <= nums[i] <= 1000
//0 <= sum(nums[i]) <= 1000
//- 1000 <= target <= 1000

//解法：将数组分为正数子集（加号）和负数子集（减号）
//设正数子集和为 P，负数子集和为 N（取绝对值）
//则有：P - N = target 且 P + N = sum（数组总和）
//解得：P = (sum + target) / 2
//原问题 ⇒ 从数组中选出若干数，使其和等于 (sum + target)/2
//dp[i][j]表示：从数组nums前i个元素选出一些数，使其和为j的个数
//对于第 i 个数字（在数组中是 nums[i-1]），我们只有两种选择：
//情况A：不选第 i 个数字
//那么前 i 个数字的和为 j 的方案数 = 前 i - 1 个数字的和为 j 的方案数
//即：dp[i][j] = dp[i - 1][j]
//情况B：选第 i 个数字（情况B只有在 j >= nums[i-1] 时才成立，否则会数组越界。）
//那么前 i - 1 个数字的和必须为 j - nums[i - 1]
//即：dp[i][j] = dp[i - 1][j - nums[i - 1]]
//

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target)
    {
        int n = nums.size();
        int sum = 0;
        for (auto& num : nums) sum += num;
        // 计算目标正数和：P = (sum + target)/2
        int aim = (sum + target) / 2;
        // 边界条件检查：
        // 1. aim不能为负数（因为要选正数子集）
        // 2. (sum + target)必须为偶数（否则无法整除）
        if (aim < 0 || (sum + target) % 2) return 0;
        vector<vector<int>> dp(n + 1, vector<int>(aim + 1));
        //不选任何数字，和为0有1种方式)
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= aim; j++)
            {
                // 不选第i个数字
                dp[i][j] = dp[i - 1][j];
                // 选第i个数字（如果容量足够）
                if (j - nums[i - 1] >= 0) dp[i][j] += dp[i - 1][j - nums[i - 1]];
            }
        return dp[n][aim];
    }
};



//4.最后一块石头的重量II
//https://leetcode.cn/problems/last-stone-weight-ii/
//有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
//每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
//如果 x == y，那么两块石头都会被完全粉碎；
//如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y - x。
//最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
//示例 1：
//输入：stones = [2, 7, 4, 1, 8, 1]
//输出：1
//解释：
//组合 2 和 4，得到 2，所以数组转化为[2, 7, 1, 8, 1]，
//组合 7 和 8，得到 1，所以数组转化为[2, 1, 1, 1]，
//组合 2 和 1，得到 1，所以数组转化为[1, 1, 1]，
//组合 1 和 1，得到 0，所以数组转化为[1]，这就是最优值。
//示例 2：
//输入：stones = [31, 26, 33, 21, 40]
//输出：5
//提示：
//1 <= stones.length <= 30
//1 <= stones[i] <= 100

//解法：
//题目要求我们每次选两块石头碰撞，最终剩下的石头重量最小。
//关键点在于
//每次碰撞相当于两块石头重量相减（大减小）。
//我们可以把石头分成两组，一组是“正”的，一组是“负”的（可以理解为加号组和减号组）。
//最终剩下的石头重量，就是这两组石头的总重量之差的绝对值。
//我们的目标是让这个差值最小。
//换句话说：
//设总重量为 sum。
//我们要选一些石头放在正组，一些放在负组，使得 正组和 - 负组和 的绝对值最小。
//设正组和为 S1，负组和为 S2，则 S1 + S2 = sum，且 S1 >= S2。
//差值 = S1 - S2 = (sum - S2) - S2 = sum - 2 * S2。
//要最小化 | sum - 2 * S2 | ，等价于让 S2 尽量接近 sum / 2（但不能超过 sum / 2）。
//所以问题转化为：
//从 stones 中选一些石头，使得它们的总重量尽量接近但不超过 sum / 2，求这个最大可能的重量 S2。
//这就是一个 0 - 1 背包问题：
//背包容量 = sum / 2
//物品重量 = 石头重量
//物品价值 = 石头重量（我们想让总重量最大）
//最终答案 = sum - 2 * maxWeight，其中 maxWeight 是背包能装的最大重量。
//计算总重量 sum。
//目标容量 target = sum / 2。
//定义 dp[j] 表示容量为 j 的背包能装的最大重量。
//遍历每个石头，更新 dp 数组（从后往前更新，避免重复选取）。
//最后 dp[target] 就是最大可能的 S2。
//答案 = sum - 2 * dp[target]。
//dp[i][j]表示：从前i个石头选出一些装入容量为 j 的背包能装的最大重量

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) 
    {
        // 计算数组总和
        int sum = 0;
        for (int stone : stones) 
        {
            sum += stone;
        }
        // 目标容量是总重量的一半
        int target = sum / 2;
        int n = stones.size();
        vector<vector<int>> dp(n + 1, vector<int>(target + 1));
        // 遍历每个石头
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= target; j++)
            {
                // 选择当前石头或不选，取最大值
                dp[i][j] = dp[i - 1][j];
                if (j - stones[i - 1] >= 0)
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
            }
        // 最终剩余石头重量 = (sum - S2) - S2 = sum - 2*S2
        return sum - 2 * dp[n][target];
    }
};